package com.ywk.base.dataStructure.algorithm;

import java.util.ArrayList;
import java.util.Arrays;

//普利姆斯
public class PrimAlgorithm {

	public static void main(String[] args) {
		String[] vertexs= {"A","B","C","D","E","F","G"};
		Graph graph = new Graph(vertexs.length);
		for(int i=0;i<vertexs.length;i++) {
			graph.addVertex(vertexs[i]);
		}
//		graph.addEdge(0, 1, 5);
//		graph.addEdge(0, 2, 7);
//		graph.addEdge(0, 6, 2);
//		graph.addEdge(1, 6, 3);
//		graph.addEdge(1, 3, 9);
//		graph.addEdge(2, 4, 8);
//		graph.addEdge(3, 5, 4);
//		graph.addEdge(4, 5, 5);
//		graph.addEdge(4, 6, 4);
//		graph.addEdge(5, 6, 6);
		
		graph.addEdge(0, 1, 12);
		graph.addEdge(0, 5, 16);
		graph.addEdge(0, 6, 14);
		graph.addEdge(1, 2, 10);
		graph.addEdge(1, 5, 7);
		graph.addEdge(2, 3, 3);
		graph.addEdge(2, 4, 5);
		graph.addEdge(2, 5, 6);
		graph.addEdge(3, 4, 4);
		graph.addEdge(4, 5, 2);
		graph.addEdge(4, 6, 8);
		graph.addEdge(5, 6, 9);
		
		graph.show();
		System.out.println(graph.repairRoad());
		System.out.println(graph.minDistance);
	}

}

class Graph{
	public ArrayList<String> vertexs;
	public int[][] edges;
	public boolean[] isVisited;
	public int minDistance;//计算修路的最小距离
	
	public Graph(int n) {
		vertexs=new ArrayList<>(n);
		isVisited=new boolean[n];
		edges=new int[n][n];
		for(int i=0;i<edges.length;i++) {
			for(int j=0;j<edges[i].length;j++) {
				edges[i][j]=Integer.MAX_VALUE;
			}
		}
	}
	
	public void addVertex(String ver) {
		vertexs.add(ver);
	}
	
	public void addEdge(int v1,int v2,int weight){
		edges[v1][v2]=weight;
		edges[v2][v1]=weight;
	}
	
	//返回与该结点相连的其他未访问过的节点的索引
	public ArrayList<Integer> getConnectVers(String ver){
		int index=vertexs.indexOf(ver);
		ArrayList<Integer> connectVers=new ArrayList<>();
		for(int i=0;i<vertexs.size();i++) {
			if(edges[index][i]!=10000 && !isVisited[i]) {
				connectVers.add(i);
			}
		}
		return connectVers;
	}
	
	//返回两个节点之间的权值
	public int getWeight(int v1,int v2) {
		return edges[v1][v2];
	}
	
	//
	public ArrayList<String> repairRoad(){
		ArrayList<String> vers=new ArrayList<String>();
		vers.add(vertexs.get(0));
		isVisited[0]=true;
		//当全部结点都处理过说明路已设计好
		while(vers.size()<vertexs.size()) {
			String ver=null;
			int minWeight=0;
			for(int v=0;v<vers.size();v++) {
				//获得相邻且未被访问过的结点的索引
				ArrayList<Integer> conVersIndex=getConnectVers(vers.get(v));
				for(int i=0;i<conVersIndex.size();i++) {
					int v1=vertexs.indexOf(vers.get(v));
					int v2=conVersIndex.get(i);
					if(minWeight==0||minWeight>edges[v1][v2]) {
						minWeight=edges[v1][v2];
						ver=vertexs.get(v2);
					}
				}
				conVersIndex.clear();
			}
			minDistance+=minWeight;
			vers.add(ver);
			isVisited[vertexs.indexOf(ver)]=true;
		}
		return vers;
		
	}
	
	public void show() {
		for(int[] link:edges) {
			System.out.println(Arrays.toString(link));
		}
	}
}